package advance.day07;


/**
 * 描述：拼成一条线的纸牌博弈问题
 * 给定一个整型数组arr，代表数值不同的纸牌排成一条线。
 * 玩家A和玩家B依次拿走 每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，
 * 玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
 *
 * @author hl
 * @version 1.0
 * @date 2020/11/13 16:19
 */
public class CardsInLine {

    public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //玩家A先手，能够获取的最大的分数
        return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
    }

    //返回第一个（当前这次）摸牌的玩家在i~j中，能够获取的最大的分数
    public static int f(int[] arr, int i, int j) {
        if (i == j) {
            return arr[i];
        }
        //当前这次选择我能获取的最大分数，并且是分数最大的一个
        return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
    }

    //返回第二个（下一次）摸牌的玩家在i~j中，另一个玩家能够能够获取的最大的分数
    public static int s(int[] arr, int i, int j) {
        if (i == j) {
            return 0;
        }
        //我绝顶聪明，选择下一个玩家在剩余牌中的能获取最大分数最小的分数
        return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
    }

    public static int win2(int[] arr) {
        int n = arr.length;
        int[][] f = new int[n][n];
        int[][] s = new int[n][n];
        //对角线遍历
//        for (int i = 0; i < arr.length; i++) {
//            f[i][i] = arr[i];
//        }
//        int index = 1;
//        while (index < n) {
//            int i = 0;
//            int j = index;
//            while (i < n - index) {
//                f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
//                s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
//                i++;
//                j++;
//            }
//            index++;
//        }
        //下到上遍历
        for (int j = 0; j < n; j++) {
            f[j][j] = arr[j];
            for (int i = j - 1; i >= 0; i--) {
                f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
                s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
            }
        }
        return Math.max(f[0][n - 1], s[0][n - 1]);
    }

    public static void main(String[] args) {
        int[] arr = {1, 9, 1};
        System.out.println(win1(arr));
        System.out.println(win2(arr));
    }
}
